import java.util.ArrayList;
import java.util.List;

public class SolveNQueens {
    // leetcode N皇后
    // https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked
    // vis1来记录列，vis2记录正斜线，vis3记录反斜线
    boolean[] vis1, vis2, vis3;
    List<List<String>> ret;
    char[][] box;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        vis1 = new boolean[n];
        vis2 = new boolean[n * 2];
        vis3 = new boolean[n * 2];
        box = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                box[i][j] = '.';
            }
        }
        backTracing(n, 0);
        return ret;
    }

    private void backTracing(int n, int row) {
        if (row >= n) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(box[i][j]);
                }
                tmp.add(sb.toString());
            }
            ret.add(tmp);
        }
        for (int i = 0; i < n; i++) {
            if (!vis1[i] && !vis2[row-i+n] && !vis3[row+i]) {
                box[row][i] = 'Q';
                vis1[i] = true;
                vis2[row-i+n] = true;
                vis3[row+i] = true;
                backTracing(n, row+1);
                box[row][i] = '.';
                vis1[i] = false;
                vis2[row-i+n] = false;
                vis3[row+i] = false;
            }
        }
    }
}
